/*
 * @lc app=leetcode.cn id=1025 lang=javascript
 *
 * [1025] 除数博弈
 */

// @lc code=start
/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function (N) {
    return N % 2 == 0//只需要证明开局偶数一定赢
};
// @lc code=end

class Solution {
    divisorGame(N) {
        vector < int > f(N + 5, false);
        f[1] = false;
        f[2] = true;
        for (let i = 3; i <= N; ++i) {
            for (let j = 1; j < i; ++j) {
                if (i % j == 0 && !f[i - j]) {//枚举 i 在 (0, i) 中 i 的因数 j，看是否存在 f[i-j] 为必败态即可,即让bob必败即可，alice取就J，那么bob只能拿i-j,若i-j必败，那么bob必胜
                    f[i] = true;
                    break;
                }
            }
        }

        return f[N];
    }
};
